from collections import Counter, deque
from math import floor
from typing import Optional
from typing import Dict, List
from functools import reduce
from datastruct import ListNode
import heapq


def wordPattern(pattern, s):
    """
    :type pattern: str
    :type s: str
    :rtype: bool
    """
    word_map = {}
    res = True
    a = [pattern.index(i) for i in pattern]
    vecs = s.split()
    b = [vecs.index(i) for i in vecs]

    return any([x == y for x, y in zip(a, b)])


def canConstruct(ransomNote: str, magazine: str):
    c1 = Counter(ransomNote)
    c2 = Counter(magazine)
    flag = True
    for key, value in c1.items():
        if key not in c2:
            flag = False
            break
        if value > c2[key]:
            flag = False
            break
    return flag


def myPosPow(x: float, n: int, cache: Dict[int, float]) -> float:
    if n == 0:
        return 1
    elif n == 1:
        return x
    else:
        if n >> 1 not in cache:
            cache[n >> 1] = myPosPow(x, n >> 1, cache)
        if n & 1:
            return cache[n >> 1] * cache[n >> 1] * x
        else:
            return cache[n >> 1] * cache[n >> 1]
    return x


def myPow(x: float, n: int) -> float:
    if n == 0:
        return 1
    else:
        cache: Dict[int, float] = {}
        return myPosPow(x, n, cache) if n > 0 else 1 / myPosPow(x, -n, cache)


def isValid(s):
    symb = []
    sym_map = dict()
    sym_map["("] = -1
    sym_map[")"] = 1
    sym_map["{"] = -2
    sym_map["}"] = 2
    sym_map["["] = -3
    sym_map["]"] = 3
    for e in s:
        if len(symb) == 0:
            symb.append(sym_map[e])
        else:
            num = symb[-1]
            current_int = sym_map[e]
            if num + current_int == 0:
                symb.pop()
            else:
                symb.append(current_int)
    if len(symb) == 0:
        return True
    else:
        return False


def frequencySort(s):
    c = Counter(s)
    result = ""
    for e in c.most_common():
        result += e[0] * e[1]
    return result


def reverseWords(s):
    lists = s.split(" ")
    filter_lists = list(filter(lambda x: x != "", lists))
    return " ".join(filter_lists[::-1])


def is_attention(list1):
    lists = sorted(list1)
    print(lists)
    for span in enumerate(lists):
        if span[0] == 0:
            begin_time = span[1][0]
            end_time = span[1][1]
        else:
            if span[1][0] < end_time:
                return False
            else:
                begin_time = span[1][0]
                end_time = span[1][1]
    return True


def findNum(nums):
    if len(nums) <= 0:
        return
    else:
        current = 0
        count = 0
        for e in nums:
            if count == 0:
                count += 1
                current = e
            else:
                if e == current:
                    count += 1
                else:
                    count -= 1
        return current


def mySqrt(x):
    if x <= 1:
        return x
    lower = 0
    upper = x
    middle = 0
    while (upper - lower) != 1:
        middle = (lower + upper) // 2
        if middle**2 == x:
            return middle
        elif middle**2 > x:
            upper = middle
        else:
            lower = middle
    return lower


def groupAnagrams(lists):
    Anagrams_dict = dict()
    for elem in lists:
        current_new = "".join(set(elem))
        if current_new in Anagrams_dict:
            Anagrams_dict[current_new].append(elem)
        else:
            Anagrams_dict[current_new] = [elem]
    return list(Anagrams_dict.values())


def gcd(a, b):
    while b != 0:
        t = b
        b = a % b
        a = t
    return a


def min_k(a, b):
    return a * b // gcd(a, b)


def summaryRanges(nums: List[int]) -> List[str]:
    left = 0
    right = 0
    size = len(nums) - 1
    res = []
    r = ""
    while left <= right and right <= size:
        while right + 1 <= size and (nums[right + 1] - nums[right] == 1
                                     or nums[right + 1] == nums[right]):
            right += 1
        if left < right:
            r = f"{nums[left]}->{nums[right]}"
        else:
            r = str(nums[left])
        right += 1
        left = right
        res.append(r)
    return res


def singleNumber(nums: List[int]) -> int:
    return reduce(lambda x, y: x ^ y, nums)


def addBinary(a: str, b: str):
    pre = 0
    v = 0
    temp = 0
    long_str = ""
    short_str = ""
    res = []
    if len(a) >= len(b):
        long_str = a
        short_str = b
    else:
        long_str = b
        short_str = a
    short_last = len(short_str) - 1
    long_last = len(long_str) - 1
    fork_last = long_last - short_last - 1

    while short_last >= 0:
        temp = eval(long_str[long_last]) + eval(short_str[short_last]) + pre
        pre = temp // 2
        v = temp % 2
        long_last -= 1
        short_last -= 1
        res.append(str(v))
    while fork_last >= 0:
        temp = eval(long_str[fork_last]) + pre
        pre = temp // 2
        v = temp % 2
        res.append(str(v))
        fork_last -= 1
    if pre == 1:
        res.append(str(1))
    return "".join(res[::-1])


def removeElement(nums: List[int], val: int) -> int:
    all_ids = []
    for idx, value in enumerate(nums):
        if value == val:
            all_ids.append(idx)
    for idx in all_ids[::-1]:
        nums.pop(idx)
    return len(nums)


def lengthOfLastWord(s: str) -> int:
    res = ""
    for elem in s.split(" ")[::-1]:
        if elem != " " and elem != "":
            res = elem
            break
    return len(res)


def isIsomorphic(s: str, t: str) -> bool:
    flag = True
    if len(s) != len(t):
        return False
    else:
        m = {}
        n = {}
        for idx, (a, b) in enumerate(zip(s, t)):
            if a not in m:
                m[a] = idx
            if b not in n:
                n[b] = idx
        for a, b in zip(s, t):
            if m[a] != n[b]:
                flag = False
                break
            else:
                continue
        return flag


def isAnagram(a: str, b: str) -> bool:
    cache = [0 for i in range(0, 26)]
    for a_value in a:
        cache[ord(a_value) - 97] += 1
    for b_value in b:
        cache[ord(b_value) - 97] -= 1
    if cache == [0 for i in range(0, 26)]:
        return True
    else:
        return False


def isHappy(n: int) -> bool:
    cache = {}
    value = 0
    while value != 1 and n not in cache:
        current_n = n
        while n > 0:
            num = n % 10
            n = n // 10
            value += num * num
        if value == 1:
            return True
        else:
            n = value
            if current_n not in cache:
                cache[current_n] = value
                value = 0
    return False


def evalRPN(list_string):
    result = []
    for e in list_string:
        if e in ["+", "*", "/", "-"]:
            op_num1 = result.pop()
            op_num2 = result.pop()

            expr_str = "{}{}{}".format(op_num2, e, op_num1)
            result.append(int(eval(expr_str)))

        else:
            result.append(e)
    return int(result[-1])


def findAnagrams(s, p):
    s_size = len(s)
    p_size = len(p)
    s_count = [0] * 26
    p_count = [0] * 26
    res = []
    if s_size < p_size:
        return res

    for i in range(p_size):
        s_count[ord(s[i]) - ord("a")] += 1
        p_count[ord(p[i]) - ord("a")] += 1

    if s_count == p_count:
        res.append(0)

    for i in range(s_size - p_size):
        s_count[ord(s[i]) - ord("a")] -= 1
        s_count[ord(s[i + p_size]) - ord("a")] += 1
        if s_count == p_count:
            res.append(i + 1)
    return res


def findTargetSumWays(nums, value):
    span = sum([abs(e) for e in nums])
    if span <= 0:
        return 0
    else:
        DP = [0 for i in range(span * 2 + 1)]
        DP[nums[0] + span] = 1
        DP[-nums[0] + span] = 1

        for num_index in range(1, len(nums)):
            temp = DP.copy()
            for start_index in range(0, 2 * span + 1):
                if start_index - nums[num_index] < 0:
                    temp[start_index] = DP[start_index + nums[num_index]]
                elif start_index + nums[num_index] > 2 * span:
                    temp[start_index] = DP[start_index - nums[num_index]]
                else:
                    temp[start_index] = (DP[start_index + nums[num_index]] +
                                         DP[start_index - nums[num_index]])
            DP = temp.copy()
        if value + span > 2 * span:
            return 0
        else:
            return DP[value + span]


def groupAnagrams(lists):
    Anagrams_dict = dict()
    for elem in lists:
        current_new = "".join(set(elem))
        if current_new in Anagrams_dict:
            Anagrams_dict[current_new].append(elem)
        else:
            Anagrams_dict[current_new] = [elem]
    return list(Anagrams_dict.values())


def isPalindrome(x: int) -> bool:
    if x < 0 or (x % 10 == 0 and x != 0):
        return False
    else:
        reverse = 0
        while x > reverse:
            s = x % 10
            x //= 10
            reverse = reverse * 10 + s
        return reverse // 10 == x or x == reverse


def plusOne(digits: List[int]) -> List[int]:
    n = len(digits)
    pre = 0
    res = deque()
    for i in range(n - 1, -1, -1):
        if i == n - 1:
            current = digits[i] + 1 + pre
            pre = current // 10
            res.appendleft(current % 10)
        else:
            current = digits[i] + pre
            pre = current // 10
            res.appendleft(current % 10)
    if pre == 1:
        res.appendleft(pre)
    return list(res)


def hammingWeight(n: int) -> int:
    c = 0
    while n != 0:
        n = n & (n - 1)
        c += 1
    return c


def findKthLargest(nums: List[int], k: int) -> int:
    heapq.heapify(nums)
    for i in range(len(nums) - k + 1):
        res = heapq.heappop(nums)
    return res
